import java.util.*;

public class BinaryTree {
    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode createTree() {
            TreeNode A = new TreeNode('A');
            TreeNode B = new TreeNode('B');
            TreeNode C = new TreeNode('C');
            TreeNode D = new TreeNode('D');
            TreeNode E = new TreeNode('E');
            TreeNode F = new TreeNode('F');
            TreeNode G = new TreeNode('G');
            TreeNode H = new TreeNode('H');
            A.left = B;
            A.right = C;
            B.left = D;
            B.right = E;
            C.left = F;
            C.right = G;
            E.right = H;
            return A;
        }
        public void preOrder(TreeNode root) {//前序
            if(root == null) return;
            System.out.print(root.val+" ");
            preOrder(root.left);
            preOrder(root.right);
        }
        public void inOrder(TreeNode root) {//中序
            if(root == null) return;
            inOrder(root.left);
            System.out.print(root.val+" ");
            inOrder(root.right);
        }
        public  void postOrder(TreeNode root){//后序
            if(root == null) return;
            postOrder(root.left);
            postOrder(root.right);
            System.out.print (root.val+" ");

        }
       /* 没有利用返回类型
       List<TreeNode>ret=new ArrayList<>();
        public List<TreeNode> preOrder2(TreeNode root){//将前序返回的节点放到列表中
            if(root == null) return ret;
            ret.add(root);
            preOrder2(root.left);
            preOrder2(root.right);
            return ret;
        }*/
    public List<TreeNode> preOrder2(TreeNode root){//前序将结果放入列表中
        List<TreeNode>ret=new ArrayList<>();
        if(root == null) return ret;
        ret.add(root);
        List<TreeNode>leftTree= preOrder2(root.left);
        ret.addAll(leftTree);
        List<TreeNode>rightTree= preOrder2(root.right);
        ret.addAll(rightTree);
        return ret;
    }
    public List<TreeNode> inOrder2(TreeNode root){//中序将结果放入列表中
        List<TreeNode>ret=new ArrayList<>();
        if(root == null) return ret;
        List<TreeNode>leftTree= inOrder2(root.left);
        ret.addAll(leftTree);
        ret.add(root);
        List<TreeNode>rightTree= inOrder2(root.right);
        ret.addAll(rightTree);
        return ret;
    }
    public List<TreeNode> postOrder2(TreeNode root){//后序将结果放入列表中
        List<TreeNode>ret=new ArrayList<>();
        if(root == null) return ret;
        List<TreeNode>leftTree= postOrder2(root.left);
        ret.addAll(leftTree);
        List<TreeNode>rightTree= postOrder2(root.right);
        ret.addAll(rightTree);
        ret.add(root);
        return ret;
    }
    public  int size=0;
    public  int nodeSize1(TreeNode root){//计算节点个数    方法1
        if(root==null) return 0;
        size++;
        nodeSize1(root.left);
        nodeSize1(root.right);
        return size;

    }
    public  int nodeSize2(TreeNode root){//方法2
        if(root==null) return 0;
        return nodeSize2(root.left)+nodeSize2(root.right)+1;
    }
     public int leafSize=0;
    public  void getLeafSize(TreeNode root){//叶子节点个数    遍历思路
        if(root==null) return ;
        if(root.left==null&&root.right==null){
            leafSize++;
        }
        getLeafSize(root.left);
        getLeafSize(root.right);
    }
    public  int  getLeafSize2(TreeNode root){//子问题思路
        if(root==null) return 0;
        if(root.left==null&&root.right==null){
            return 1;
        }
        return getLeafSize2(root.left)+getLeafSize2(root.right);


    }
    public  int getKLeveCount(TreeNode root,int k){//得到k层的节点数
        if(root==null) return 0;
        if(k==1){
            return 1;
        }
        return getKLeveCount(root.left,k-1)+getKLeveCount(root.right,k-1);
    }
    public  int getHeight(TreeNode root){//得到树的高度     利用整棵树的高度等于root左树的高度最大值或root右树高毒的最大值+1
        if(root==null) return 0;
         int leftHeight=getHeight(root.right);
         int rigthHeight=getHeight(root.right);
         return (leftHeight>rigthHeight)?leftHeight+1:rigthHeight+1;

    }
    public  boolean find(TreeNode root,char key){//判断二叉树中是否有key这个个字符
        if(root==null){
            return false;
        }
        if(root.val==key){
            return true;
        }
        boolean leftval=find(root.left,key);
        if(leftval==true){
            return  true;
        }
        boolean rightval=find(root.right,key);
        if(rightval==true){
            return  true;
        }
        return false;

    }
    public  boolean isSameTree(TreeNode p,TreeNode q){//该方法是用来判断俩个二叉树是否相等   相等分结构相等和值相等
        if(p==null&&q!=null||p!=null&&q==null){//结构不同
            return  false;
        }
        if(p==null&&q==null){
            return true;
        }
        if(p.val== q.val){
            return true;
        }
        return isSameTree(p.left,q.left)&& isSameTree(p.right,q.right);
    }
    public  boolean isSubtree(TreeNode root,TreeNode subRoot){//该方法主要是用来判断一个树是不是另一颗树的子树
        if(root==null){//必须要判断是否为空，否则会出现空指针异常     时间复杂度是（s*n）假设root有n个节点  subRoot有s个节点
            return false;
        }
        if(isSameTree(root,subRoot)){
            return true;
        }
        if(isSameTree(root.left,subRoot)){
            return true;
        }
        if(isSameTree(root.right,subRoot)){
            return true;
        }
        return  false;

    }
    public  TreeNode invertTree(TreeNode root){//该方法是用来将一个二叉树交换的
        if(root==null){
            return null;
        }
        TreeNode tmp=root.left;//交换左右子树的指向
        root.left=root.right;
        root.right=tmp;
        invertTree(root.left);
        invertTree(root.right);
        return  root;
    }
    public  boolean isBalanced(TreeNode root){//判断这棵树是不是高度平衡二叉树   左右子树的高度差小于等于1  但这种方法时间复杂的达到n*n
        if(root==null){
            return  true;
        }
        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);
        return  Math.abs(leftHeight-rightHeight)<=1&&isBalanced(root.left)&&isBalanced(root.right);

    }
    public  int getHeight1(TreeNode root){//这个方法主要是用来配合下面这个方法写的
        if(root==null) return 0;
        int leftHeight=getHeight1(root.right);
        int rigthHeight=getHeight1(root.right);
        if(leftHeight>=0&&rigthHeight>=0&&Math.abs(leftHeight-rigthHeight)<=1){
            return Math.max(leftHeight,rigthHeight)+1;
        }else {
            return -1;
        }
    }
    public boolean isBalanced1(TreeNode root){//
        if(root==null){
            return  true;
        }
        return getHeight1(root)>=0;

    }
    public  boolean isSymmetricChild(TreeNode p,TreeNode q){//该方法用来判断一个二叉树是不是对称的  p根节点的左节点  q根节点的右节点
        if(p==null&&q!=null||p!=null&&q==null){
            return  false;
        }
        if(p==null&&q==null){
            return true;
        }
        if(p.val!=q.val){
            return  false;
        }
        return  isSymmetricChild(p.left,q.right)&&isSymmetricChild(p.right,q.left);
    }
    public  void levelOrder(TreeNode root){//层序遍历二叉树     将每遍历的一个节点放到队中，记录这个节点，然后删除这个节点同时也打印 然后再遍历根节点的左右子树
        if(root==null){
            return;
        }
        Queue <TreeNode>queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur=queue.poll();
            System.out.println(cur.val+" ");
            if(cur.left!=null){
                queue.offer(cur.left);
            }
            if(cur.right!=null){
                queue.offer(cur.right);
            }
        }

    }
    public  List<List<TreeNode>> levelNode1(TreeNode root){//将层序遍历的节点返回到列表中
        List<List<TreeNode>> ret=new ArrayList<>();//此时ret下标为0时代表第一层的节点列表返回  ret下表为1时代表第二场节点以列表的形式返回等等
        if(root==null){
            return ret;
        }
        Queue<TreeNode>queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size= queue.size();//计算当前队列的大小
            List<TreeNode>tmp=new ArrayList<>();//临时列表变量，放每层的节点
            while(size!=0){
                TreeNode cur=queue.poll();
                tmp.add(cur);
                size--;
                if(cur.left!=null){
                    queue.offer(cur.left);

                }
                if(cur.left!=null){
                    queue.offer(cur.right);
                }
            }
            ret.add(tmp);//每一层的节点数相加
        }
        return ret;

    }
    public  boolean isCompleteTree(TreeNode root){
        if(root==null){
            return true;
        }
        Queue<TreeNode>queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur=queue.poll();
            if(cur!=null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else{
                break;
            }
        }
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            if(cur!=null){
                return false;
            }
        }
        return true;


    }
    public  TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){//求最近公共祖先节点 ①p或者q是其中的一个祖先点②p或者去在跟节点的一侧③p根根节点的俩测
        if(root==null){
            return null;

        }
        if(root==p||root==q){
            return root;
        }
        TreeNode leftTree=lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree=lowestCommonAncestor(root.right,p,q);
        if(leftTree!=null&&rightTree!=null){
            return root;
        }else if(leftTree!=null){
            return leftTree;
        }else {
            return rightTree;
        }


    }
    private  boolean getPath(TreeNode root, TreeNode node, Stack stack){//找到root到node之间路劲上所有节点存储在stack中
        if(root==null||node==null){
            return false;
        }
        stack.push(root);
        if (root == node) {
            return true;
        }
        boolean flg=getPath(root.left,node,stack);
        if(flg){
            return true;
        }
        boolean flg2=getPath(root.right,node,stack);
        if(flg2){
            return true;
        }
        stack.pop();
        return false;
    }
    public  TreeNode lowestCommonAncestor2(TreeNode root,TreeNode p,TreeNode q){//求最近公共祖先节点
        if(root==null){
            return null;
        }
        Stack<TreeNode>stackP=new Stack<>();
        Stack<TreeNode>stackQ=new Stack<>();
        getPath(root,p,stackP);
        getPath(root,q,stackQ);
        int sizeP=stackP.size();
        int sizeQ=stackQ.size();
        if(sizeP>sizeQ){
            int size=sizeP-sizeQ;
            while(size!=0){
                stackP.pop();
                size--;
            }
        }else{
            int size=sizeQ-sizeP;
            while(size!=0){
                stackQ.pop();
                size--;

        }
    }
        while (!stackP.isEmpty()&&!stackQ.isEmpty()) {
            if (stackP.peek().equals(stackQ.peek())) {
                return stackP.peek();

            }
            stackP.pop();
            stackQ.pop();
        }
        return null;

    }
    //该方法主要是根据前序和中序遍历构建二叉树
    /*public  int priIndex;
    public  TreeNode buildTree(int []preorder,int []inorder){
        return buildTreeChild(preorder,inorder,0,inorder.length-1);

    }


    private  TreeNode buildTreeChild(int []preorder,int []inorder,int inbegin,int inend){
        //没有左树或者没有右树
        if(inbegin>inend){
            return null;
        }
        //创建根节点
        TreeNode root=new TreeNode(preorder[priIndex]);
        //从中序遍历中找到根节点所在下标，
        int rootIndex=findIndex(inorder,inbegin,inend,preorder[priIndex]);
        if(rootIndex==-1){
            return null;
        }
        priIndex++;
        //创建左子树和右子树
        root.left=buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
        root.right=buildTreeChild(preorder,inorder,rootIndex+1,inend);
        return  root;

    }
    private  int findIndex(int []inorder,int inbegin,int inend,int key){
        for (int i = inbegin; i <=inend ; i++) {
            if(inorder[i]==key){
                return i;
            }
        }
        return -1;
    }*/
    //根据后序盒中序创建二叉树
    /*public  int postIndex;
    public  TreeNode buildTree(int []inorder,int []postorder){
        postIndex=postorder.length-1;
        return buildTreeChild( postorder,inorder,0,inorder.length-1);

    }


    private  TreeNode buildTreeChild(int []postorder,  int []inorder ,int inbegin,int inend){
        //没有左树或者没有右树
        if(inbegin>inend){
            return null;
        }
        //创建根节点
        TreeNode root=new TreeNode(postorder[postIndex]);
        //从中序遍历中找到根节点所在下标，
        int rootIndex=findIndex(inorder,inbegin,inend,postorder[postIndex]);
        if(rootIndex==-1){
            return null;
        }
        postIndex--;
        //创建左子树和右子树

        root.right=buildTreeChild(postorder,inorder,rootIndex+1,inend);
        root.left=buildTreeChild(postorder,inorder,inbegin,rootIndex-1);
        return  root;

    }
    private  int findIndex(int []inorder,int inbegin,int inend,int key){
        for (int i = inbegin; i <=inend ; i++) {
            if(inorder[i]==key){
                return i;
            }
        }
        return -1;
    }

*/
    //二叉树创建字符串
    private  void tree2strChild(TreeNode t,StringBuilder stringBuilder){
        if(t==null){
            return;
        }
        stringBuilder.append(t.val);
        if(t.left!=null){
            stringBuilder.append("(");
            tree2strChild(t.left,stringBuilder);
            stringBuilder.append(")");
        }
        else{
            if(t.right==null){
                return ;
            }
            else{
                stringBuilder.append("()");
            }


        }
        if(t.right!=null){
            stringBuilder.append("(");
            tree2strChild(t.right,stringBuilder);
            stringBuilder.append(")");

        }
        else{
            return;
        }

    }
    //该方法主要是实现非递归前序遍历   用栈来实现
    public  void preOrderNor(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode>stack=new Stack<>();
        TreeNode cur=root;
        TreeNode top=null;//top为栈顶元素
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                System.out.println(cur.val+" ");
                cur=cur.left;
            }
            top=stack.pop();
            cur=top.right;
        }


    }
    //该方法主要是实现非递归中序遍历   用栈来实现
    public  void inOrderNor(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode>stack=new Stack<>();
        TreeNode cur=root;
        TreeNode top=null;//top为栈顶元素
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }

            top=stack.pop();
            System.out.print(top.val+" ");
            cur=top.right;
        }


    }
    //该方法主要是实现非递归后序遍历   用栈来实现
    public  void postOrderNor(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode>stack=new Stack<>();
        TreeNode cur=root;
        TreeNode prev=null;

        TreeNode top=null;//top为栈顶元素
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            top=stack.peek();
            if(top.right==null||top.right==prev){
                stack.pop();
                System.out.print(top.val+" ");
            }else{
                cur=top.right;
            }
        }
    }

}
